//////////#include<iostream>
//////////#include<set>
//////////#include<map>
//////////#include<queue>
//////////using namespace std;
//////////class A
//////////{
//////////public:
//////////	void p()
//////////	{
//////////		cout << "A" << endl;
//////////	}
//////////	virtual ~A()
//////////	{
//////////		p();
//////////	}
//////////};
//////////class B : public A
//////////{
//////////public:
//////////	void p()
//////////	{
//////////		cout << "B" << endl;
//////////	}
//////////	~B()
//////////	{
//////////		A::p();
//////////		p();
//////////	}
//////////};
//////////void test(priority_queue<int, vector<int>, greater<int>>& l)
//////////{
//////////	l.push(1);
//////////	l.push(2);
//////////	l.push(3);
//////////	l.push(4);
//////////	cout << l.top() << endl;
//////////}
//////////class Solution {
//////////public:
//////////	int majorityElement(vector<int>& nums)
//////////	{
//////////		map<int, int> m;
//////////		int count = 1;
//////////		for (size_t i = 0; i < nums.size(); i++)
//////////		{
//////////			if (i - 1 >= 0||nums[i - 1] != nums[i])
//////////			{
//////////				m.insert(make_pair(nums[i], count));
//////////			}
//////////			else
//////////				count++;
//////////		}
//////////		int x = 0;
//////////		for (const auto& e : m)
//////////		{
//////////			if (e.second == nums.size() / 2)
//////////			{
//////////				x = e.first;
//////////				break;
//////////			}
//////////		}
//////////		return x;
//////////	}
//////////};
////////////class Solution {
////////////public:
////////////	int majorityElement(vector<int>& nums)
////////////	{
////////////		multiset<int> m;
////////////		for (auto e : nums)
////////////			m.insert(e);
////////////		int ret = 0;
////////////		for (auto s : m)
////////////		{
////////////			ret = m.count(s);
////////////			if (ret > nums.size() / 2)
////////////				return s;
////////////		}
////////////		
////////////	}
////////////};
//////////int main()
//////////{
//////////	/*A* pa = new B;
//////////	delete pa;*/
//////////	/*map<int, int> m;
//////////	m.insert(make_pair(1, 1));
//////////	set<int> s;
//////////	s.insert(1);
//////////	for (auto e : s)
//////////	{
//////////		cout << e << endl;
//////////	}
//////////	map<int, int>::iterator it = m.begin();
//////////	cout << it->first << "," << it->second << endl;
//////////	vector<int> v;
//////////	v.push_back(1);
//////////	v.push_back(2);
//////////	v.push_back(3);
//////////	v.push_back(4);
//////////	v.push_back(5);*/
//////////	//priority_queue<int,vector<int>,less<int>> q(v.begin(),v.end());
//////////	//test(q);
//////////	// 
//////////	//cout << q.top() << endl;
//////////	/*class Solution {
//////////	public:
//////////		int majorityElement(vector<int>& nums)
//////////		{
//////////			map<int, int> m;
//////////			int count = 1;
//////////			for (size_t i = 0; i + 1 < nums.size(); i++)
//////////			{
//////////				if (nums[i + 1] != nums[i])
//////////				{
//////////					m.insert(make_pair(nums[i], count));
//////////				}
//////////				else
//////////					count++;
//////////			}
//////////			int x = 0;
//////////			for (const auto& e : m)
//////////			{
//////////				if (e.second == nums.size() / 2)
//////////				{
//////////					x = e.first;
//////////					break;
//////////				}
//////////			}
//////////			return x;
//////////		}
//////////	};*/
//////////	vector<int> v;
//////////	v.push_back(3);
//////////	v.push_back(1);
//////////	v.push_back(3);
//////////
//////////	int ret=Solution().majorityElement(v);
//////////	
//////////	return 0;
//////////}
////////#include<iostream>
////////#include<queue>
////////using namespace std;
////////void test(priority_queue<int,vector<int>,greater<int>>& l)
////////{
////////	l.push(2);
////////}
////////int main()
////////{
////////	priority_queue<int,vector<int>,greater<int>> q;
////////	q.push(1);
////////	q.push(1);
////////	q.push(1);
////////	q.push(1);
////////	test(q);
////////	return 0;
////////}
//////#include<iostream>
//////#include<vector>
//////#include<queue>
////////using namespace std;
////////  struct TreeNode 
////////  {
////////      int val;
////////      TreeNode *left;
////////      TreeNode *right;
////////      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
////////  };
////////class Solution {
////////public:
////////    void print(TreeNode* root, vector<TreeNode*>& p)
////////    {
////////        if (root == nullptr)
////////            return;
////////        print(root->left, p);
////////        p.push_back(root);
////////        print(root->right, p);
////////    }
////////    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p)
////////    {
////////        vector<TreeNode*> v;
////////        print(root, v);
////////        TreeNode* cur = nullptr;
////////        size_t i = 0;
////////        for (i = 0; i < v.size(); i++)
////////        {
////////            if (v[i] == p)
////////            {
////////                cur = v[i + 1];
////////                break;
////////            }
////////        }
////////        if (i == v.size())
////////            return nullptr;
////////        else
////////            return cur;
////////    }
////////};
////////int main()
////////{
////////    TreeNode* root1 = new TreeNode(1);
////////    TreeNode* root2 = new TreeNode(2);
////////    TreeNode* root3 = new TreeNode(3);
////////    root2->left = root1;
////////    root2->right = root3;
////////    TreeNode* p = root1;
////////    Solution().inorderSuccessor(root2, p);
////////    return 0;
////////}
//////#include<queue>
//////#include<vector>
//////#include<iostream>
//////#include<map>
//////#include<set>
//////using namespace std;
////////class KthLargest {
////////public:
////////    KthLargest(int k, vector<int>& nums)
////////    {
////////        kmax = k;
////////        for (auto& e : nums)
////////            m[e]++;
////////    }
////////
////////    int add(int val)
////////    {
////////        m[val]++;
////////        vector<pair<int, int>> v;
////////        for (auto& s : m)
////////            v.push_back(s);
////////        int max = kmax;
////////        int i = 0;
////////        while (1)
////////        {
////////            if (max > v[i].second)
////////            {
////////                max = max - v[i].second;
////////                i++;
////////            }
////////            else
////////                return v[i].first;
////////        }
////////        return 0;
////////    }
////////private:
////////    map<int, int, greater<int>> m;
////////    int kmax;
////////};
////////int main()
////////{
////////    vector<int> v;
////////    v.push_back(4);
////////    v.push_back(5);
////////    v.push_back(8);
////////    v.push_back(2);
////////    KthLargest s(3, v);
////////    s.add(3);
////////    s.add(5);
////////    s.add(10);
////////    s.add(9);
////////    s.add(4);
////////    return 0;
////////}
//////class Solution {
//////public:
//////    vector<int> topKFrequent(vector<int>& nums, int k)
//////    {
//////        map<int, int> m;
//////        for (auto& e : nums)
//////            m[e]++;
//////        vector<int> v;
//////        for (auto& s : m)
//////            v.push_back(s.second);
//////        sort(v.begin(), v.end(), greater<int>());
//////        vector<int> vv;
//////        int i = 0;
//////        for (auto& d : m)
//////        {
//////            for (i = 0; i < k; i++)
//////            {
//////                if (d.second == v[i])
//////                    vv.push_back(d.first);
//////            }
//////        }
//////        return vv;
//////    }
//////};
//////int main()
//////{
//////    vector<int> v;
//////    v.push_back(1);
//////    v.push_back(2);
//////    Solution().topKFrequent(v, 2);
//////    return 0;
//////}
////#include<iostream>
////using namespace std;
//// struct TreeNode 
//// {
////      int val;
////      TreeNode *left;
////      TreeNode *right;
////      TreeNode() : val(0), left(nullptr), right(nullptr) {}
////      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
////      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
////  };
//// 
//////class Solution {
//////public:
//////    bool earse(TreeNode*& root, int key)
//////    {
//////        if (root == nullptr)
//////            return false;
//////        TreeNode* cur = root;
//////        if (key < cur->val)
//////            return earse(cur->left, key);
//////        else if (key > cur->val)
//////            return earse(cur->right, key);
//////        else
//////        {
//////            if (cur->left == nullptr)
//////            {
//////                TreeNode* del = root;
//////                root = root->right;
//////                delete del;
//////                del = nullptr;
//////                return true;
//////            }
//////            else if (cur->right == nullptr)
//////            {
//////                TreeNode* del = root;
//////                root = root->left;
//////                delete del;
//////                del = nullptr;
//////                return true;
//////            }
//////            else
//////            {
//////                TreeNode* min = root->right;
//////                while (min->left)
//////                    min = min->left;
//////                std::swap(min->val, root->val);
//////                return earse(root->right, key);
//////            }
//////        }
//////    }
//////    TreeNode* deleteNode(TreeNode* root, int key)
//////    {
//////        if (root == nullptr)
//////            return nullptr;
//////        earse(root, key);
//////        return root;
//////    }
//////};
//// /**
//// * Definition for a binary tree node.
//// * struct TreeNode {
//// *     int val;
//// *     TreeNode *left;
//// *     TreeNode *right;
//// *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
//// * };
//// */
////#include<stack>
////#include<string.h>
//// //class Solution {
//// //public:
//// //    bool findpath(TreeNode* root, TreeNode* ret, stack<TreeNode*>& path)
//// //    {
//// //        if (root == nullptr)
//// //            return false;
//// //        path.push(root);
//// //        if (ret == root)
//// //            return true;
//// //        bool left = findpath(root->left, ret, path);
//// //        bool right = findpath(root->right, ret, path);
//// //        if (!(left || right))
//// //            path.pop();
//// //        return left || right;
//// //    }
//// //    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
//// //    {
//// //        if (root == nullptr)
//// //            return nullptr;
//// //        stack<TreeNode*> qpath;
//// //        stack<TreeNode*> ppath;
//// //        findpath(root, q, qpath);
//// //        findpath(root, p, ppath);
//// //        if (ppath.size() != qpath.size())
//// //        {
//// //            size_t x = ppath.size() > qpath.size() ? ppath.size() : qpath.size();
//// //            if (x = qpath.size())
//// //            {
//// //                while (x--)
//// //                    qpath.pop();
//// //            }
//// //            else
//// //            {
//// //                while (x--)
//// //                    ppath.pop();
//// //            }
//// //        }
//// //        while (!ppath.empty())
//// //        {
//// //            if (ppath.top() == qpath.top())
//// //                return ppath.top();
//// //            ppath.pop();
//// //            qpath.pop();
//// //        }
//// //        return nullptr;
//// //    }
//// //};
////#include<set>
////#include<string>
//////class Solution {
//////public:
//////    int strStr(string haystack, string needle)
//////    {
//////        const char* hay = haystack.c_str();
//////        const char* neel = needle.c_str();
//////        const char* p = strstr(hay, neel);
//////        if (p == nullptr)
//////            return -1;
//////        return p - hay;
//////    }
//////};
/////**
//// * Definition for a binary tree node.
//// * struct TreeNode {
//// *     int val;
//// *     TreeNode *left;
//// *     TreeNode *right;
//// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//// * };
//// */
////#include<vector>
////#include<string>
////#include<stdlib.h>
//////class Solution {
//////public:
//////    bool add(TreeNode* root, int targetSum, int sum, vector<vector<int>>& vv, int& i)
//////    {
//////        if (root == nullptr && sum != targetSum)
//////        {
//////            return false;
//////        }
//////        if (root == nullptr && sum == targetSum)
//////        {
//////            return true;
//////        }
//////        vv[i].push_back(root->val);
//////        sum += root->val;
//////        bool left = add(root->left, targetSum,sum, vv, i);
//////        bool right = add(root->right, targetSum,sum, vv, i);
//////        if (!(left || right))
//////        {
//////            if (!vv[i].empty())
//////                vv[i].pop_back();
//////        }
//////        if (left || right)
//////        {
//////            i++;
//////            vv.push_back(vector<int>());
//////        }
//////        return left || right;
//////    }
//////    vector<vector<int>> pathSum(TreeNode* root, int targetSum)
//////    {
//////        int i = 0;
//////        int sum = 0;
//////        vector<vector<int>> vv;
//////        vv.push_back(vector<int>());
//////        add(root, targetSum, sum, vv, i);
//////        return vv;
//////    }
//////};
////#include<queue>
////#include<string>
//////class Solution {
//////public:
//////    string kthLargestNumber(vector<string>& nums, int k)
//////    {
//////        priority_queue<long long> q;
//////        for (const auto& e : nums)
//////        {
//////            const char* p = e.c_str();
//////            q.push(atoll(p));
//////        }
//////        k -= 1;
//////        while (k--)
//////            q.pop();
//////        return std::to_string(q.top());
//////    }
//////};
//////class Solution {
//////public:
//////    int deleteGreatestValue(vector<vector<int>>& grid)
//////    {
//////        for (auto& e : grid)
//////        {
//////            sort(e.begin(), e.end());
//////        }
//////        vector<int> v;
//////        v.resize(2);
//////        int col = 0;
//////        int row = 0;
//////        int i = 0;
//////        int sum = 0;
//////        for (row=0;row<(int)grid.size();row++)
//////        {
//////            for (col = 0; col < (int)grid[row].size(); col++)
//////            {
//////                if (!grid[row].empty())
//////                {
//////                    v[i] = grid[row].back();
//////                    grid[row].pop_back();
//////                    i++;
//////                }
//////                if (i > 2)
//////                {
//////                    sum = sum + v[0] > v[1] ? v[0] : v[1];
//////                    i = 0;
//////                }
//////            }
//////        }
//////        return sum;
//////    }
//////};
////#include<map>
////#include<set>
//////int main()
//////{
//////    TreeNode* root1 = new TreeNode(1);
//////    TreeNode* root2 = new TreeNode(2);
//////    TreeNode* root3 = new TreeNode(1);
//////    root2->left = root1;
//////    root2->right = root3;
//////    TreeNode* p = root1;
//////    vector<vector<int>> vv = { {1,2,4 }, { 3,3,1 } };
//////    Solution().deleteGreatestValue(vv);
//////    //Solution().pathSum(root2, 3);
//////    /*int arr[] = { 1,1,1,3,3,2 };
//////    set<int> s;
//////    for (auto e : arr)
//////        s.insert(e);
//////    for (auto d : s)
//////        cout << d << " ";
//////    cout << endl;*/
//////    map<int, int> m;
//////    m[1]++;
//////    return 0;
//////}
////#include<iostream>
////#include<vector>
////#include<algorithm>
////using namespace std;
//////81
//////class Solution {
//////public:
//////    bool search(vector<int>& nums, int target)
//////    {
//////        sort(nums.begin(), nums.end());
//////        int left = 0;
//////        int right = (int)(nums.size()) - 1;
//////        int mid = left + ((right - left) / 2);
//////        while (left <= right)
//////        {
//////            if (nums[mid] == target)
//////                return true;
//////            else if (nums[mid] < target)
//////            {
//////                left = mid + 1;
//////                mid = left + ((right - left) / 2);
//////            }
//////            else
//////            {
//////                right = mid - 1;
//////                mid = left + ((right - left) / 2);
//////            }
//////        }
//////        return false;
//////    }
//////};
//////class Solution {
//////public:
//////    int removeDuplicates(vector<int>& nums)
//////    {
//////        map<int, int> m;
//////        for (auto& e : nums)
//////            m[e]++;
//////        int len = 0;
//////        for (auto& s : m)
//////        {
//////            if (s.second > 2)
//////                s.second = 2;
//////            len += s.second;
//////        }
//////        nums.resize(len);
//////        int i = 0;
//////        for (auto& d : m)
//////        {
//////            while (d.second--)
//////                nums[i++] = d.first;
//////        }
//////        return len;
//////    }
//////};
////struct ListNode 
////{
////      int val;
////      ListNode *next;
////      ListNode() : val(0), next(nullptr) {}
////      ListNode(int x) : val(x), next(nullptr) {}
////      ListNode(int x, ListNode *next) : val(x), next(next) {}
////};
////// 
//////class Solution {
//////public:
//////    ListNode* deleteDuplicates(ListNode* head)
//////    {
//////        map<int, int> m;
//////        ListNode* cur = head;
//////        while (cur)
//////        {
//////            m[cur->val]++;
//////            cur = cur->next;
//////        }
//////        for (auto& e : m)
//////        {
//////            if (e.second >= 2)
//////                e.second = 0;
//////        }
//////        ListNode* phead = nullptr;
//////        for (auto& s : m)
//////        {
//////            if (s.second != 0)
//////            {
//////                if (phead == nullptr)
//////                {
//////                    phead = new ListNode(s.first);
//////                    cur = phead;
//////                }
//////                else
//////                {
//////                    while (cur->next)
//////                        cur = cur->next;
//////                    cur->next = new ListNode(s.first);
//////                }
//////            }
//////        }
//////        return phead;
//////    }
//////};
//////class Solution {
//////public:
//////    vector<int> searchRange(vector<int>& nums, int target)
//////    {
//////        vector<int> v;
//////        v.resize(2, -1);
//////        int left = 0;
//////        int right = (int)(nums.size() - 1);
//////        int mid = left + ((right - left) / 2);
//////        while (left <= right)
//////        {
//////            if (nums[mid] == target)
//////            {
//////                if (mid == 0 && nums.size() != 1)
//////                {
//////                    if ((mid + 1) < (int)(nums.size()) && nums[mid] == nums[mid + 1])
//////                    {
//////                        v[0] = mid;
//////                        v[1] = mid + 1;
//////                    }
//////                    else
//////                        v[0] = v[1] = mid;
//////                }
//////                else
//////                {
//////                    if (nums.size() != 1
//////                        && (mid + 1) < (int)(nums.size())
//////                        && nums[mid] == nums[mid + 1])
//////                    {
//////                        v[0] = mid;
//////                        v[1] = mid + 1;
//////                    }
//////                    else if (nums.size() != 1
//////                        && (mid + 1) < (int)(nums.size())
//////                        && (mid - 1) >= 0
//////                        && (mid - 1) < (int)(nums.size())
//////                        && nums[mid] < nums[mid + 1]
//////                        && nums[mid] != nums[mid - 1])
//////                        v[1] = v[0] = mid;
//////                    else if (nums.size() != 1
//////                        && (mid + 1) < (int)(nums.size())
//////                        && (mid - 1) >= 0
//////                        && (mid - 1) < (int)(nums.size())
//////                        && nums[mid] < nums[mid + 1] && nums[mid] == nums[mid - 1])
//////                    {
//////                        v[0] = mid - 1;
//////                        v[1] = mid;
//////                    }
//////                    else if (nums.size() == 1)
//////                        v[1] = v[0] = mid;
//////                }
//////                       
//////                return v;
//////            }
//////            else if (nums[mid] < target)
//////            {
//////                left = mid + 1;
//////                mid = left + ((right - left) / 2);
//////            }
//////            else
//////            {
//////                right = mid - 1;
//////                mid = left + ((right - left) / 2);
//////            }
//////        }
//////        return v;
//////    }
//////};
////class Solution {
////public:
////    ListNode* arrivecur(ListNode* head, int k)
////    {
////        ListNode* cur = head;
////        k -= 1;
////        while (k--)
////        {
////            if (cur != nullptr)
////                cur = cur->next;
////        }
////        return cur;
////    }
////    ListNode* reverseBetween(ListNode* head, int left, int right)
////    {
////        if (head == nullptr)
////            return nullptr;
////        ListNode* leftp = arrivecur(head, left);
////        ListNode* rightp = arrivecur(head, right);
////        while (left < right)
////        {
////            if (leftp != nullptr && rightp != nullptr)
////                swap(leftp->val, rightp->val);
////            left++;
////            right--;
////            leftp = arrivecur(head, left);
////            rightp = arrivecur(head, right);
////        }
////        return head;
////    }
////};
////int main()
////{
////    vector<int> v = { 1 ,4 };
////   /* bool ret = Solution().search(v, 0);
////    cout << ret << endl;*/
////    ListNode* head = new ListNode(1);
////    ListNode* head1 = new ListNode(2);
////    ListNode* head2= new ListNode(3);
////    // ListNode* head3 = new ListNode(3);
////    ListNode* head4 = new ListNode(4);
////    //ListNode* head5 = new ListNode(4);
////    ListNode* head6 = new ListNode(5);
////    head->next = head1;
////    head1->next = head2;
////    head2->next = head4;
////    head4->next = head6;
////    Solution().reverseBetween(head, 2, 4);
////    return 0;
////}
//#include <iostream>
//using namespace std;
//class Date
//{
//public:
//    Date()
//        : day(0)
//        , month(0)
//        , year(0)
//    {}
//    ~Date()
//    {
//        day = month = year = 1;
//    }
//private:
//    int day;
//    int month;
//    int year;
//};
//int main()
//{
//    Date* p = new Date;
//    delete p;
//    return 0;
//}
#include<iostream>
#include<vector>
using namespace std;
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
class Solution {
public:
    void find(TreeNode* root, vector<int>& v)
    {
        if (root == nullptr)
            return;
        find(root->left, v);
        find(root->right, v);
        if (root->left == nullptr && root->right == nullptr)
            v.push_back(root->val);
    }
    bool leafSimilar(TreeNode* root1, TreeNode* root2)
    {
        vector<int> v;
        find(root1, v);
        vector<int> v2;
        find(root2, v2);
        int i = 0;
        if (v.size() == v2.size())
        {
            for (auto e : v)
            {
                if (e != v2[i++])
                    return false;
            }
            return true;
        }
        else
            return false;
    }
};
int main()
{
    TreeNode* root1 = new TreeNode(1);
    TreeNode* root2 = new TreeNode(2);
    TreeNode* root3 = new TreeNode(3);
    TreeNode* root4 = new TreeNode(1);
    TreeNode* root5 = new TreeNode(3);
    TreeNode* root6 = new TreeNode(2);
    root1->left = root2;
    root1->right = root3;
    root4->left = root5;
    root4->right = root6;
    Solution().leafSimilar(root1, root4);

    return 0;
}